//
//  ArrayTool.m
//  Test
//
//  Created by 喂！ on 2018/6/29.
//  Copyright © 2018年 喂！. All rights reserved.
//

#import "ArrayTool.h"

@implementation ArrayTool

/**
 冒泡排序
 */
- (NSMutableArray *)bubbleSortWithMutableArray:(NSMutableArray *)mutableArray Ascending:(BOOL)ascending
{
    for (int i = 0; i<mutableArray.count-1; i++) {
        for (int k = 0; k < mutableArray.count- 1 - i; k++) {
            if (ascending) {
                if (mutableArray[k] < mutableArray[k + 1]) {
                    [mutableArray exchangeObjectAtIndex:k withObjectAtIndex:k + 1];
                }
            }else
            {
                if (mutableArray[k] > mutableArray[k + 1]) {
                    [mutableArray exchangeObjectAtIndex:k withObjectAtIndex:k + 1];
                }
            }
        }
    }
    return mutableArray;
}

/**
 选择排序
 
 @param mutableArray 排序的目标数组
 */
- (NSMutableArray *)selectionSortWithMutableArray:(NSMutableArray *)mutableArray Ascending:(BOOL)ascending
{
    for (int i = 0; i < mutableArray.count; i++) {
        int index = i;
        for (int k = i+1; k<mutableArray.count; k++) {
            
            if (ascending) {
                if ([mutableArray[k] integerValue] < [mutableArray[index] integerValue]) {
                    index = k;
                }
            }else
            {
                if ([mutableArray[k] integerValue] > [mutableArray[index] integerValue]) {
                    index = k;
                }
            }
            
        }
        if (index != i) {
            [mutableArray exchangeObjectAtIndex:index withObjectAtIndex:i];
        }
        
    }
    return mutableArray;
}

/**
 快速排序
 */
- (NSMutableArray *)quickSortArray:(NSMutableArray *)array withLeftIndex:(NSInteger)leftIndex andRightIndex:(NSInteger)rightIndex
{
    if (leftIndex >= rightIndex) {//如果数组长度为0或1时返回
        return array;
    }
    
    NSInteger i = leftIndex;
    NSInteger j = rightIndex;
    //记录比较基准数
    NSInteger key = [array[i] integerValue];
    
    while (i < j) {
        /**** 首先从右边j开始查找比基准数小的值 ***/
        while (i < j && [array[j] integerValue] >= key) {//如果比基准数大，继续查找
            j--;
        }
        //如果比基准数小，则将查找到的小值调换到i的位置
        array[i] = array[j];
        
        /**** 当在右边查找到一个比基准数小的值时，就从i开始往后找比基准数大的值 ***/
        while (i < j && [array[i] integerValue] <= key) {//如果比基准数小，继续查找
            i++;
        }
        //如果比基准数大，则将查找到的大值调换到j的位置
        array[j] = array[i];
        
    }
    
    //将基准数放到正确位置
    array[i] = @(key);
    
    /**** 递归排序 ***/
    //排序基准数左边的
//    [self quickSortArray:array withLeftIndex:leftIndex andRightIndex:i - 1];
//    //排序基准数右边的
//    [self quickSortArray:array withLeftIndex:i + 1 andRightIndex:rightIndex];
    
    return array;
}



@end
